package Array.easy;

import java.util.HashMap;

/**
 * 1. 问题描述
 *      数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
 *
 * 2. 算法分析
 *      我们需要返回数组中超过数组长度一般数量的元素(如果没有，返回-1)
 *      摩尔投票法
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 主要元素 {
    public static void main(String[] args) {
        System.out.println(1 ^ 1 ^ 3 ^ 3 ^ 3);
    }

    /**
     * 返回数组的主要元素
     * 采用hashmap计数 key为nums中的元素，对应的value为该元素在数组中出现的次数
     * 时间复杂度和空间复杂度都比较高，不是一个比较好的算法实现
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        if(nums.length == 0) {return -1;}
        if(nums.length == 1) {return nums[0];}
        // 如果nums中确实有主要元素，我们只需要对nums从下到大排序，然后返回数组的中间值即可
        // 问题是如果nums没有主要元素，我们如何判断呢?
        // 使用hashmap计数
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])) {
                map.put(nums[i],map.get(nums[i])+1);
            } else {
                map.put(nums[i],1);
            }
        }
        for(int item : nums) {
            if(map.get(item) > nums.length / 2) {
                return item;
            }
        }
        return -1;
    }

    /**
     * 当前代码和上述的不同之处在于我们省略了最后的for循环而是在计数的同时加上判断
     * 但是在leetcode上面提交之后的时间复杂度任然很高，也不是一个比较好的算法，能否不借助
     * 中间的数据结构来实现上述问题的求解?
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        if(nums.length == 0) {return -1;}
        if(nums.length == 1) {return nums[0];}
        int len = nums.length;
        int condition = len / 2;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++) {
            if(map.containsKey(nums[i])) {
                map.put(nums[i],map.get(nums[i])+1);
                if (map.get(nums[i]) > condition) {
                    return nums[i];
                }
            } else {
                map.put(nums[i],1);
            }
        }
        return -1;
    }

    /**
     * 算法3： 摩尔投票法
     *      1. 什么是摩尔投票法?
     *        1. 抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，
     *           如果两个投票相同，则累加可抵消的次数；
     *        2. 计数阶段：在抵消阶段最后得到的抵消计数只要不为0，那这个候选人是有可能超过一半的票数的，
     *          为了验证，则需要遍历一次，统计票数，才可确定。
     *          备注：对于1/3，1/4.....1/n，做法就是设置n-1个投票候选人，采用摩尔投票的方法进行操作。
     *
     *      注意：在使用投票法我们最后求出的temp并不一定满足票数超过一般
     *      例如 1 1 2 2 1 2 1 1 2 2 3 3 3，显然1的次数最多5但是任然没有超过数组的一半，所以我们
     *      需要在最后进行判断
     *
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        // 投票阶段
        int temp = nums[0]; // 假设为当前的众数
        int count = 1; // 当前众数出现的次数
        for (int i = 1; i < nums.length; i++) {
            if (temp == nums[i]) {
                count++;
            } else {
                count--;
            }
            // 判断当前的count是否为0
            if (count == 0) {
                temp = nums[i];
                count = 1;
            }
        }
        // 验证是否满足要求
        int t = nums.length / 2 + 1;
        count = 0;
        for (int num : nums) {
            if (num == temp) count++;
            if (count == t) return temp;
        }
        return -1;
    }


}
